public class HeapSort {

	public static void sort( Comparable[] arr ) {
		buildHeap( arr );

		int last = arr.length - 1;
		while ( last > 0 ) {
			swap( arr, 0, last );
			--last;
			percolateDown( arr, 0, last );
		}
	}

	private static void buildHeap( Comparable[] arr ) {
		int last = arr.length - 1;
		for ( int i = arr.length / 2 - 1; i >= 0; --i ) {
			percolateDown( arr, i, last ); 
		}
	}

	private static void swap( Comparable[] arr, int i, int j ) {
		Comparable tmp = arr[ i ];
		arr[ i ] = arr[ j ];
		arr[ j ] = tmp;
	}

	private static void percolateDown( Comparable[] arr, int i, int last ) {
		int child = 2 * i + 1;

		if ( child < last && arr[child+1].compareTo(arr[child]) > 0) {
			++child;
		}

		if ( child <= last && arr[i].compareTo(arr[child]) < 0 ) {
			swap( arr, i, child );
			percolateDown( arr, child, last );
		}
	}

	public static void main( String[] args ) {
		Integer[] arr = new Integer[ args.length ];

		for ( int i = 0; i < args.length; ++i ) {
			arr[ i ] = new Integer( args[ i ] );
		}

		HeapSort.sort( arr );

		for ( int i = 0; i < arr.length; ++i ) {
			System.out.println( arr[ i ] );
		}
	}
	
}